from .bitcarry import lowBit as _lowBit


class Quene:
    """先进先出队列"""

    def __init__(self, initdata: list = []) -> None:
        self.contain: list = initdata

    def push(self, data):
        self.contain.append(data)
        return self

    def pop(self, pos=0):
        if len(self) == 0:
            return None
        temp = self.contain[pos]
        del self.contain[pos]
        return temp

    def __len__(self):
        return len(self.contain)

    def __str__(self):
        return f"quene({str(self.contain)})"


class Deque(Quene):
    """双端队列"""

    def __init__(self, initdata: list = []) -> None:
        super().__init__(initdata)

    def pushleft(self, data):
        self.contain.insert(0, data)
        return self

    def popright(self):
        return super().pop(pos=-1)

    def __str__(self):
        return f"deque({str(self.contain)})"


class Stack(Quene):
    """先进后出堆栈"""

    def __init__(self, initdata: list = []) -> None:
        super().__init__(initdata)

    def pop(self):
        return super().pop(pos=-1)

    def __str__(self):
        return f"stack({str(self.contain)})"


class treeArray:
    """树状数组"""

    def __init__(self, initdata: list = None) -> None:
        if initdata is None:
            initdata = []
        self.leng: int = len(initdata)
        self.contain: list = [0] * (self.leng + 1)
        for i in range(self.leng):
            self.add(i + 1, initdata[i])

    def add(self, p: int, k: float):
        while p <= self.leng:
            self.contain[p] += k
            p += _lowBit(p)
        return self

    def __sum(self, p: int):
        if p < 0:
            return 0
        p = min(p, self.leng)
        sum = 0
        while p:
            sum += self.contain[p]
            p -= _lowBit(p)
        return sum

    def __getpoint(self, p: int):
        """单点查询"""
        return self.__sum(p + 1) - self.__sum(p)

    def __getsum(self, l: int, r: int):
        """区间查询"""
        return self.__sum(r) - self.__sum(l)

    def __getitem__(self, p):
        if isinstance(p, int):
            if p < 0 or p > self.leng - 1:
                raise Exception("Index out of range.")
            return self.__getpoint(p)
        elif isinstance(p, slice):
            start = 0 if p.start is None else p.start
            stop = self.leng if p.stop is None else p.stop
            if start < 0 or stop > self.leng:
                raise Exception("Index out of range.")
            return self.__getsum(start, stop)

    def __str__(self):
        temp = str(self.contain[1:]) if self.leng > 0 else "[]"
        return f"treeArray({temp})"

    def __len__(self):
        return self.leng


class segmentTree:
    """线段树"""

    def __init__(self, initdata: list) -> None:
        self.__initdata = initdata
        self.leng: int = len(initdata)
        if self.leng == 0:
            raise Exception("Data can't be none.")
        self.contain: list = [0] * self.leng * 3
        self.__build(1, self.leng, 1)
        del self.__initdata

    def __build(self, s: int, t: int, p: int):
        """对 [s,t] 区间建立线段树,当前根的编号为 p"""
        if s == t:
            self.contain[p] = self.__initdata[s - 1]
            return
        m = (t + s) >> 1
        self.__build(s, m, p * 2)
        self.__build(m + 1, t, p * 2 + 1)
        self.contain[p] = self.contain[p * 2] + self.contain[(p * 2) + 1]

    def __sum(self, l: int, r: int, s: int, t: int, p: int):
        """[l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号"""
        if l <= s and t <= r:
            return self.contain[p]
        m = (t + s) >> 1
        sum = 0
        if l <= m:
            sum += self.__sum(l, r, s, m, p * 2)
        if r > m:
            sum += self.__sum(l, r, m + 1, t, p * 2 + 1)
        return sum

    def __getsum(self, l: int, r: int):
        """区间查询"""
        return self.__sum(l, r, 1, self.leng, 1)

    def __getpoint(self, p: int):
        """单点查询"""
        return self.__sum(p + 1, p + 1, 1, self.leng, 1)

    def __getitem__(self, p):
        if isinstance(p, int):
            if p < 0 or p > self.leng - 1:
                raise Exception("Index out of range.")
            return self.__getpoint(p)
        elif isinstance(p, slice):
            start = 0 if p.start is None else p.start
            stop = self.leng if p.stop is None else p.stop
            if start < 0 or stop > self.leng:
                raise Exception("Index out of range.")
            return self.__getsum(start, stop)

    def __str__(self):
        temp = str(self.contain[1:]) if self.leng > 0 else "[]"
        return f"segmentTree({temp})"

    def __len__(self):
        return self.leng
